package heap;

import java.util.Arrays;

public class HeapSort {
    public static void createHeap (int[] array) {
        //定义倒数第二层的结点
        int parent= (array.length-1-1)/2;
        for(int i=parent;i>=0;--i){
            shiftDown(array,i,array.length);
        }

    }

    private static void shiftDown(int[] array, int parent, int length) {
        int child =2*parent+1;
        //判断有无左子节点
        while(child<length){
            //取左右节点中的最大值
            if(child+1<length){
                if(array[child]<array[child+1]){
                    child++;
                }
            }
            //将较大值与父节点进行比较
            if(array[parent]<array[child]){
                swap(array,parent,child);
            }
            else{
                break;
            }
            //不断向下循环
            parent=child;
            child=2*parent+1;
        }

    }

    private static void swap(int[] array, int parent, int child) {
        int temp=array[parent];
        array[parent]=array[child];
        array[child]=temp;

    }

    public static void sort(int[] array) {
        //建立堆
        createHeap(array);
        int child = array.length - 1;
        //对调头结点和根结点
        while (child >= 0) {
            swap(array, 0, child);
            shiftDown(array, 0, child);
            child--;
        }


    }

    public static void main(String[] args) {
        int [] array = { 27,15,19,18,28,34,65,49,25,37 };
        sort(array);
        System.out.println(Arrays.toString(array));
    }
}